#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct node {
	int data;
	struct node *left;
	struct node *right;
} node_t;

void tree_insert(node_t **root, node_t *new)
{
	node_t **pos = root;

	while (*pos != NULL) {
		if (new->data >= (*pos)->data)
		 	pos = &(*pos)->right;
		else
			pos = &(*pos)->left;
	}
	*pos = new;
}

void create_tree(node_t **root, 
	int *data, int n)
{
	node_t *new;
	int i;

	for (i = 0; i < n; i++) {
		new = (node_t *)malloc(sizeof(node_t));
		memset(new, 0, sizeof(node_t));

		new->data = data[i];
		tree_insert(root, new);
	}
}

void post_scan_1(node_t *node)
{
	if (node->left)
		post_scan_1(node->left);
	if (node->right)
		post_scan_1(node->right);
	printf("%d \t", node->data);
}

/* START:: code for stack */
#define STACK_SIZE 32

typedef struct stack {
	node_t *data[STACK_SIZE];
	int pos;
} stack_t;

int push(stack_t *s, node_t *new)
{
	if (s->pos >= STACK_SIZE)
		return -1;
	s->data[s->pos++] = new;
	return 0;
}

node_t *pop(stack_t *s)
{
	if (s->pos > 0)
		return s->data[--s->pos];
	return NULL;
}

node_t *top(stack_t *s)
{
	if (s->pos > 0)
		return s->data[s->pos - 1];
	return NULL;
}

int empty(stack_t *s)
{
	if (s->pos == 0)
		return 1;
	return 0;
}

void init_stack(stack_t *s)
{
	s->pos = 0;
	memset(s->data, 0, sizeof(node_t *) * STACK_SIZE);
}

/* END:: code for stack */
void post_scan_2(node_t *root)
{
	node_t *cur = root, *pre = NULL; 
	stack_t s[1];

	init_stack(s);

	while (cur && !empty(s)) {
		while (cur->left) {
			push(s, cur->left);
			cur = cur->left;
		}
		cur = top(s);
		if (!cur->right && pre == cur->right) {
			printf("%d \t", cur->data);
			pop(s);
			pre = cur;
			cur = NULL;
		} else {
			cur = cur->right;
		}
	}
}

#define N 8
int main ()
{
	node_t *root;
	int datas[N] = {3, 5, 8, 2, 1, 7, 9, 6};

	create_tree(&root, datas, N);
	printf("\n");
	post_scan_1(root);
	printf("\n");
	post_scan_1(root);
	printf("\n");
	return 0;
}

